/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/merge-number
   @Language: C++
   @Datetime: 19-06-25 10:01
   */

class Solution {
public:
	/**
	 * @param numbers: the numbers
	 * @return: the minimum cost
	 */
	int mergeNumber(vector<int> &numbers) {
		// Write your code here
		priority_queue<int,vector<int>,greater<int> > pq;
		for(int i=0; i<numbers.size(); pq.push(numbers[i++]));
		int cost=0;
		for(int a, b; pq.size()>1; pq.push(a+b)){
			a=pq.top();
			pq.pop();
			b=pq.top();
			pq.pop();
			cost+=a+b;
		}
		return cost;
	}
};
